#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File        :   206.反转链表.py    
@Contact     :   lhouctcs@163.com
@License     :   MIT
@Time        :   2023/2/4 13:11
@Author      :   lhou 
@Version     :   0.1.0
@Description :
"""
from typing import Optional


# import lib
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None
        while (cur != None):
            temp = cur.next  # 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur.next = pre  # 反转
            # 更新pre、cur指针
            pre = cur
            cur = temp
        return pre

    def reverseList_2(self, head: ListNode) -> ListNode:

        def reverse(pre, cur):
            if not cur:
                return pre

            tmp = cur.next
            cur.next = pre

            return reverse(cur, tmp)

        return reverse(None, head)
